package 困难.动态规划.背包.零一背包;

/**
 * 给你一个正整数数组 nums 和一个整数 k 。
 * 分区 的定义是：将数组划分成两个有序的 组 ，并满足每个元素 恰好 存在于 某
 * 一个 组中。如果分区中每个组的元素和都大于等于 k ，则认为分区是一个好分区。
 * 返回 不同 的好分区的数目。由于答案可能很大，请返回对 109 + 7 取余 后的结果。
 * 如果在两个分区中，存在某个元素 nums[i] 被分在不同的组中，则认为这两个分区不同。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/number-of-great-partitions
 */
public class 好分区的数目_2518 {

    public static void main(String[] args) {

        //[1,2,3,4]
        //4
        System.out.println(countPartitions(new int[]{3, 3, 3}, 4));

    }

    /**
     * 逆向思维+01背包
     * 1，每个元素可以放在 组1和组2 中，有两种方案，假设 nums 有 n 个
     * 元素，那么全部方案数量为，2 的 n 次方
     * 2，可以先计算出坏方案的总数量，然后 total - bad
     * 问题可以转化为在 nums 中找出几个数 sum<k 的方案数
     * 因为找出来的数可以放在 组1或者组2，所以上面的方案数* 2 为坏方案的总数量
     * 3，动态规划
     * 子问题：
     * dp[i][j] 表示在 nums 的前 i（非索引！） 个数中选取的元素和为 j 的方案数为多少
     * 状态转移方程：
     * 选择 nums[i] 的方案数，dp[i-1][j-nums[i]]
     * 不选择 nums[i] 的方案数，dp[i-1][j]
     * dp[i][j] = dp[i-1][j-nums[i]] + dp[i-1][j]
     * 初始化值：
     * dp[0][0] = 1 , 只有一种方案，什么都不选，总和为 0
     * dp[0][1,k-1] , 没有方案使得和 >0
     */
    public static int countPartitions(int[] nums, int k) {
        int sum = 0, mod = 1000000007;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            if (sum >= 2 * k) break;
        }
        if (sum < 2 * k) {
            return 0;
        }

        int[][] dp = new int[nums.length + 1][k];
        dp[0][0] = 1;

        for (int i = 1; i < nums.length + 1; i++) {
            for (int j = 0; j < k; j++) {
                if (j - nums[i - 1] >= 0) {
                    dp[i][j] = dp[i - 1][j - nums[i - 1]];
                }
                dp[i][j] = (dp[i][j] + dp[i - 1][j]) % mod;
            }
        }

        int total = 1;
        for (int i = 0; i < nums.length; i++) {
            total = (2 * total) % mod;
        }

        for (int j = 0; j < k; j++) {
            // 避免出现负数
            total = (total - dp[nums.length][j] * 2 % mod + mod) % mod;
        }
        return total;
    }

}
